home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / agrep / follow.c.z / follow.c
C/C++ Source or Header  |  1997-09-09  |  5KB  |  257 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* the functions in this file take a syntax tree for a regular
  3.    expression and produce a DFA using the McNaughton-Yamada
  4.    construction.                        */
  5.  
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <stdlib.h>
  9. #include <unistd.h>
  10. #include "re.h"
  11.  
  12. #define TRUE    1
  13.  
  14. extern Pset pset_union(); 
  15. extern int pos_cnt;
  16. extern Re_node parse();
  17.  
  18. Re_lit_array lpos; 
  19.  
  20.  
  21. /*  extend_re() extends the RE by adding a ".*(" at the front and a "("
  22.     at the back.                               */
  23.  
  24. char *extend_re(s)
  25. char *s;
  26. {
  27.     char *s1;
  28.  
  29.     s1 = malloc((unsigned) strlen(s)+4+1);
  30.     return strcat(strcat(strcpy(s1, ".*("), s), ")");
  31. }
  32.  
  33. void free_pos(fpos, pos_cnt)
  34. Pset_array fpos;
  35. int pos_cnt;
  36. {
  37.     Pset tpos, pos;
  38.     int i;
  39.  
  40.     if ((fpos == NULL) || (*fpos == NULL)) return;
  41.     for (i=0; i<pos_cnt; i++) {
  42.         pos = (*fpos)[i];
  43.         while (pos != NULL) {
  44.             tpos = pos;
  45.             pos = pos->nextpos;
  46.             free(tpos);
  47.         }
  48.     }
  49.     free(fpos);
  50. }
  51.  
  52. /* Function to clear out a Ch_Set */
  53. void free_cset(cset)
  54. Ch_Set cset;
  55. {
  56.     Ch_Set tset;
  57.  
  58.     while (cset != NULL) {
  59.         tset = cset;
  60.         cset = cset->rest;
  61.         free(tset->elt);
  62.         free(tset);
  63.     }
  64. }
  65.  
  66. /* Function to clear out the tree of re-nodes */
  67. void free_re(e)
  68. Re_node e;
  69. {
  70.     if (e == NULL) return;
  71.  
  72. /*
  73.  * Was creating "reading freed memory", "freeing unallocated/freed memory"
  74.  * errors. So abandoned it. Leaks are now up by 60B/call to 80B/call
  75.  * -bg
  76.  *
  77.     {
  78.     Pset tpos, pos;
  79.     int tofree = 0;
  80.  
  81.     if ((Lastpos(e)) != (Firstpos(e))) tofree = 1;
  82.     pos = Lastpos(e);
  83.     while (pos != NULL) {
  84.         tpos = pos;
  85.         pos = pos->nextpos;
  86.         free(tpos);
  87.     }
  88.     Lastpos(e) = NULL;
  89.  
  90.     if (tofree) {
  91.         pos = Firstpos(e);
  92.         while (pos != NULL) {
  93.             tpos = pos;
  94.             pos = pos->nextpos;
  95.             free(tpos);
  96.         }
  97.         Firstpos(e) = NULL;
  98.     }
  99.     }
  100. */
  101.  
  102.     switch (Op(e)) {
  103.     case EOS:
  104.         if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
  105.         free(Lit(e));
  106.         break;
  107.     case OPSTAR:
  108.         free_re(Child(e));
  109.         break;
  110.     case OPCAT:
  111.         free_re(Lchild(e));
  112.         free_re(Rchild(e));
  113.         break;
  114.     case OPOPT:
  115.         free_re(Child(e));
  116.         break;
  117.     case OPALT:
  118.         free_re(Lchild(e));
  119.         free_re(Rchild(e));
  120.         break;
  121.     case LITERAL:
  122.         if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
  123.         free(Lit(e));
  124.         break;
  125.     default: 
  126.         fprintf(stderr, "free_re: unknown node type %d\n", Op(e));
  127.     }
  128.     free(e);
  129.     return;
  130. }
  131.  
  132.  
  133. /* mk_followpos() takes a syntax tree for a regular expression and
  134.    traverses it once, computing the followpos function at each node
  135.    and returns a pointer to an array whose ith element is a pointer
  136.    to a list of position nodes, representing the positions in
  137.    followpos(i).                            */
  138.  
  139. void mk_followpos_1(e, fpos)
  140. Re_node e;
  141. Pset_array fpos;
  142. {
  143.     Pset pos;
  144.     int i;
  145.  
  146.     switch (Op(e)) {
  147.     case EOS: 
  148.         break;
  149.     case OPSTAR:
  150.         pos = Lastpos(e);
  151.         while (pos != NULL) {
  152.             i = pos->posnum;
  153.             (*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i]);
  154.             pos = pos->nextpos;
  155.         }
  156.         mk_followpos_1(Child(e), fpos);
  157.         break;
  158.     case OPCAT:
  159.         pos = Lastpos(Lchild(e));
  160.         while (pos != NULL) {
  161.             i = pos->posnum;
  162.             (*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i]);
  163.             pos = pos->nextpos;
  164.         }
  165.         mk_followpos_1(Lchild(e), fpos);
  166.         mk_followpos_1(Rchild(e), fpos);
  167.         break;
  168.     case OPOPT:
  169.         mk_followpos_1(Child(e), fpos);
  170.         break;
  171.     case OPALT:
  172.         mk_followpos_1(Lchild(e), fpos);
  173.         mk_followpos_1(Rchild(e), fpos);
  174.         break;
  175.     case LITERAL:
  176.         break;
  177.     default: 
  178.         fprintf(stderr, "mk_followpos: unknown node type %d\n", Op(e));
  179.     }
  180.     return;
  181. }
  182.  
  183. Pset_array mk_followpos(tree, npos)
  184. Re_node tree;
  185. int npos;
  186. {
  187.     int i;
  188.     Pset_array fpos;
  189.  
  190.     if (tree == NULL || npos < 0) return NULL;
  191.     fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));
  192.     if (fpos == NULL) return NULL;
  193.     for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;
  194.     mk_followpos_1(tree, fpos);
  195.     return fpos;
  196. }
  197.  
  198. /* mk_poslist() sets a static array whose i_th element is a pointer to
  199.    the RE-literal at position i.  It returns 1 if everything is OK,  0
  200.    otherwise.                                */
  201.  
  202. /* init performs initialization actions; it returns -1 in case of error,
  203.    0 if everything goes OK.                        */
  204.  
  205. int init(s, table)
  206. char *s; 
  207. int table[32][32];
  208. {
  209.     Pset_array fpos;
  210.     Re_node e;
  211.     Pset l;
  212.     int i, j;
  213.     char *s1;
  214.  
  215.     if ((s1 = extend_re(s)) == NULL) return -1;
  216.     if ((e = parse(s1)) == NULL) {
  217.         free(s1);
  218.         return -1;
  219.     }
  220.     free(s1);
  221.     if ((fpos = mk_followpos(e, pos_cnt)) == NULL) {
  222.         free_re(e);
  223.         return -1;
  224.     }
  225.     for (i = 0; i <= pos_cnt; i += 1) {
  226. #ifdef Debug
  227.         printf("followpos[%d] = ", i);
  228. #endif
  229.         l = (*fpos)[i];
  230.         j = 0;
  231.         for ( ; l != NULL; l = l->nextpos)  {
  232. #ifdef Debug
  233.             printf("%d ", l->posnum);
  234. #endif
  235.             table[i][j] = l->posnum;
  236.             j++;
  237.         } 
  238. #ifdef Debug
  239.         printf("\n");
  240. #endif
  241.     }
  242. #ifdef Debug
  243.     for (i=0; i <= pos_cnt; i += 1)  {
  244.         j = 0;
  245.         while (table[i][j] != 0) {
  246.             printf(" %d ", table[i][j]);
  247.             j++;
  248.         }
  249.         printf("\n");
  250.     }
  251. #endif
  252.     free_pos(fpos, pos_cnt);
  253.     free_re(e);
  254.     return (pos_cnt);
  255. }
  256.  
  257.